package Math;//给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）
//。 
//
// 
//
// 示例 1： 
//
// 
//输入：left = 5, right = 7
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：left = 0, right = 0
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：left = 1, right = 2147483647
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= left <= right <= 2³¹ - 1 
// 
// Related Topics 位运算 👍 377 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class rangeBitwiseAnd {
    public int rangeBitwiseAnd(int left, int right) {
        //给定两个整数，我们要找到它们对应的二进制字符串的公共前缀。
        //通过同时右移位两个数字，直到他们相等，此时是公共前缀，记录移位次数，最后还原
        int shift = 0;
        while(left<right){
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }

    public int rangeBitwiseAnd1(int m, int n) {
        while (m < n) {
            // 抹去最右边的 1
            n = n & (n - 1);
        }
        return n;
    }

}
//leetcode submit region end(Prohibit modification and deletion)
